package Intermediate_algorithm.Math;

import org.junit.Test;

/*
阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0

提示：
0 <= n <= 104
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xwehi5/
 */
public class _02阶乘后的零 {

    @Test
    public void test() {
        System.out.println(trailingZeroes(13));
    }

    //WA  数值太大无法存储
    public int trailingZeroes(int n) {
        if (n == 0) return 0;
        int count = 0;
        Long helper = helper(n);
        while (helper != 0) {
            if (helper % 10 == 0){
                count++;
                helper = helper / 10;
            }else {
                break;
            }
        }
        return count;
    }

    public Long helper(int n){
        Long res = 1L;
        for (int i = 1; i <= n; i++) {
            res *= i;
        }
        return res;
    }

    //官解：方法一：数学
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/factorial-trailing-zeroes/solutions/1360892/jie-cheng-hou-de-ling-by-leetcode-soluti-1egk/
     */
    class Solution {
        public int trailingZeroes(int n) {
            int ans = 0;
            for (int i = 5; i <= n; i += 5) {
                for (int x = i; x % 5 == 0; x /= 5) {
                    ++ans;
                }
            }
            return ans;
        }
    }

    //官解：方法二：优化计算
    class Solution2 {
        public int trailingZeroes(int n) {
            int ans = 0;
            while (n != 0) {
                n /= 5;
                ans += n;
            }
            return ans;
        }
    }


}
